package com.ma.service;

public class recursion {


    /**
     * 如果递归满足T(N)=a*T(N/b)+O(N^d)
     * 1) log(b,a)>d O(N^log(b,a))
     * 2) log(b,a)<d O(N^d)
     * 3) log(b,a)=d O(N^d*logN)
     *
     * (
     *  T(N/b):子规模
     *  a:调用次数
     *  O(N^d): 其它操作(排除递归操作)的时间复杂度
     * )
     *如：
     *      二分法：T(N)=2*T(N/2)+O(N^0)
     *
     */

    public static int getMax(int[] arr){
        return process(arr,0,arr.length-1);
    }

    //利用二分法在arr[L....R]上求最大值
    private static int process(int[] arr, int L, int R) {
        if(L==R){
            return arr[L];
        }
        int mid=L+((R-L)>>1);
        int leftMax=process(arr,L,mid);
        int rightMax=process(arr,mid+1,R);
        return Math.max(leftMax,rightMax);
    }


}
